package array;

//find the maximum sum possible in an array of positive integers by selecting the 
//elements in such a way that no two elements are next to each other
public class MaxSumNoNext {

  public static int maxSum(int[] data) {
    if (data == null)
      return 0;
    int n = data.length;
    int[] f = new int[n];
    f[0] = data[0];
    f[1] = Math.max(data[0], data[1]);
    for (int i = 2; i < n; i++) {
      f[i] = Math.max(f[i - 2] + data[i], f[i - 1]);
    }

    return f[n - 1];
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(maxSum(new int[] { -1, -2, -5, -4, -5, -6, -7 }));
  }

}
